﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace www.coursera.algo.org._5.QuickSort
{
    public class QuickSorter
    {
        public static int count = 0;
        public static List<double> SortFirst(List<double> inputArray, int start, int end)
        {
            if (end - start <= 0)
            {
                return inputArray;
            }
            count = count + end - start;
            //choose pivot

            
            double pivot = inputArray[start];
            int i = start + 1;

            for (int j = start + 1; j <= end; j++)
            {

                if (inputArray[j] < pivot)
                {


                    inputArray = swapValue(inputArray, j, i);
                    i = i + 1;
                }

            }


            inputArray = swapValue(inputArray, i - 1, start);
            //count = count + start+end-2;
            SortFirst(inputArray, start, i - 2);

            SortFirst(inputArray, i, end);

            return inputArray;
        }
        public static List<double> SortLast(List<double> inputArray, int start, int end)
        {
            if (end - start <=0)
            {
                return inputArray;
            }
            count = count + end - start ;
            //choose pivot
            
            inputArray = swapValue(inputArray, end, start);
            double pivot = inputArray[start];
            int i = start + 1;
            
            for (int j = start + 1; j <=end; j++)
            {
                
                if (inputArray[j] < pivot)
                {

                    
                    inputArray = swapValue(inputArray, j, i);
                    i = i + 1;
                }

            }


            inputArray = swapValue(inputArray, i - 1, start);
            //count = count + start+end-2;
            SortLast(inputArray, start, i - 2);

            SortLast(inputArray, i, end);

            return inputArray;
        }

        public static List<double> SortMedian(List<double> inputArray, int start, int end)
        {
            if (end - start <= 0)
            {
                return inputArray;
            }
            count = count + end - start;
            //choose pivot

            inputArray = median(inputArray,start,end);
            double pivot = inputArray[start];
            int i = start + 1;

            for (int j = start + 1; j <= end; j++)
            {

                if (inputArray[j] < pivot)
                {


                    inputArray = swapValue(inputArray, j, i);
                    i = i + 1;
                }

            }


            inputArray = swapValue(inputArray, i - 1, start);
            //count = count + start+end-2;
            SortMedian(inputArray, start, i - 2);

            SortMedian(inputArray, i, end);

            return inputArray;
        }



        public static List<double> median(List<double> inputArray,int start, int end)
        {
            if (end - start < 2)
            {
                return inputArray;
            }

            Dictionary<int,double> x = new Dictionary<int,double>();
            x.Add(start, inputArray[start]);
            x.Add(end,inputArray[end]);
            if((end-start+1)%2==0)
            {
                x.Add(start-1 + Convert.ToInt32((end - start + 1) / 2), inputArray[start-1 + Convert.ToInt32((end - start + 1) / 2)]);
            }
            else
            {
                x.Add(start-1 + Convert.ToInt32(((end - start + 1) / 2) + 1), inputArray[start-1 + Convert.ToInt32(((end - start + 1) / 2) + 1)]);
            }
            


            int[] sortedDict =
                (from entry in x orderby entry.Value ascending select entry).Select(p => p.Key).ToArray();

            swapValue(inputArray, sortedDict[1], start);

            return inputArray;


        }

        private static List<double> swapValue(List<double> inputArray, int index1, int index2)
        {
            double tempValue = inputArray[index1];
            inputArray[index1] = inputArray[index2];
            inputArray[index2] = tempValue;
            return inputArray;
        }

        public static void SortRandom(List<double> a, int left, int right)
        {
            int i = left;
            int j = right;
            double leftString = a[i];
            double rightString = a[j];
            double pivotValue = ((left + right) / 2);
            double middle = a[Convert.ToInt32(pivotValue)];
            double temp;
            
            while (i <= j)
            {

                while (a[i].CompareTo(middle) < 0)
                {
                    i++;
                    count = count + 1;
                    leftString = a[i];
                }
                while (a[j].CompareTo(middle) > 0)
                {
                    j--;
                    count = count + 1;
                    rightString = a[j];
                }
                if (i <= j)
                {
                    temp = a[i];
                    a[i++] = a[j];
                    a[j--] = temp;
                }
            }
            if (left < j)
            {
                SortRandom(a, left, j);
            }
            if (i < right)
            {
                SortRandom(a, i, right);
            }
        }
    }
}
